﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CodeTester
{
    /// <summary>
    /// 二叉树结点
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class TreeNode<T>
    {
        public T Data { get; set; }

        public TreeNode<T> LChild { get; set; }
        public TreeNode<T> RChild { get; set; }

        public TreeNode() { }
        public TreeNode(T data)
        {
            this.Data = data;
        }

        public TreeNode(T data, TreeNode<T> lchild, TreeNode<T> rchild)
        {
            this.Data = data;
            this.LChild = lchild;
            this.RChild = rchild;
        }

    }

    /// <summary>
    /// 二叉树实现
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class BTree<T>
    {
         // 二叉树的根节点
        private TreeNode<T> root;
        public TreeNode<T> Root
        {
            get
            {
                return this.root;
            }
        }

        public BTree() { }

        public BTree(T data)
        {
            this.root = new TreeNode<T>(data);
        }

        // Method02:在节点p下插入左孩子节点的data
        public void InsertLeft(TreeNode<T> p, T data)
        {
            TreeNode<T> tempNode = new TreeNode<T>(data);
            tempNode.LChild = p.LChild;
            p.LChild = tempNode;
        }

        // Method03:在节点p下插入右孩子节点的data
        public void InsertRight(TreeNode<T> p, T data)
        {
            TreeNode<T> tempNode = new TreeNode<T>(data);
            tempNode.RChild = p.RChild;
            p.RChild = tempNode;
        }

        // Method04:删除节点p下的左子树
        public TreeNode<T> RemoveLeft(TreeNode<T> p)
        {
            if (p == null || p.LChild == null)
            {
                return null;
            }

            TreeNode<T> tempNode = p.LChild;
            p.LChild = null;
            return tempNode;
        }

        // Method05:删除节点p下的右子树
        public TreeNode<T> RemoveRight(TreeNode<T> p)
        {
            if (p == null || p.RChild == null)
            {
                return null;
            }

            TreeNode<T> tempNode = p.RChild;
            p.RChild = null;
            return tempNode;
        }

        // Method06:判断节点p是否叶子节点
        public bool IsLeafNode(TreeNode<T> p)
        {
            if (p == null)
            {
                return false;
            }

            return p.LChild == null && p.RChild == null;
        } 
        /// <summary>
        /// 前序遍历
        /// </summary>
        /// <param name="node"></param>
        public void PreOrder(TreeNode<T> node)
        {
            if (node != null)
            {
                Console.WriteLine(node.Data);
                PreOrder(node.LChild);
                PreOrder(node.RChild);
            }
        }
        /// <summary>
        /// 中序遍历
        /// </summary>
        /// <param name="node"></param>
        public void MidOrder(TreeNode<T> node)
        {
            if (node != null)
            {
                MidOrder(node.LChild);
                Console.WriteLine(node.Data);
                MidOrder(node.RChild);
            }
        }
        /// <summary>
        /// 后序遍历
        /// </summary>
        /// <param name="node"></param>
        public void PostOrder(TreeNode<T> node)
        {
            if (node != null)
            {
                PostOrder(node.LChild);
                PostOrder(node.RChild);
                Console.WriteLine(node.Data);
            }
        }
    }
}
